/*!
 Temelia - Hash set implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/common.h"
#include "include/hash_set.h"
#include "include/vector.h"
#include "include/linked_list.h"
#include <stdlib.h>

struct _hash_set_t
{
	// Vector of linked lists, each containing keys with the same hash.
	vector_t back_bone;
};

hash_set_t hash_set_new(int size)
{
	int i;
	hash_set_t hash_set;

	hash_set = (struct _hash_set_t *) _new(sizeof(struct _hash_set_t));

	_ASSERT(hash_set, ==, NULL, INVALID_INPUT, NULL);

	hash_set->back_bone = vector_new(size);

	_ASSERT(hash_set->back_bone, ==, NULL, NULL_POINTER, NULL);

	for (i = 0; i < size; i++)
		vector_push_back(hash_set->back_bone, linked_list_new());

	return hash_set;
}

void hash_set_clear(hash_set_t hash_set)
{
	int size, i;

	_ASSERT(hash_set, ==, NULL, NULL_POINTER,);

	size = vector_get_size(hash_set->back_bone);

	for (i = 0; i < size; i++)
	{
		linked_list_delete(vector_get_key_at(hash_set->back_bone, i));
		vector_set_key_at(hash_set->back_bone, i, linked_list_new());
	}
}

void hash_set_delete(hash_set_t hash_set)
{
	int i, size;
	_ASSERT(hash_set, ==, NULL, NULL_POINTER,);

	size = vector_get_capacity(hash_set->back_bone);
	for (i = 0; i < size; i++)
		linked_list_delete(vector_get_key_at(hash_set->back_bone, i));

	vector_delete(hash_set->back_bone);
	_delete(hash_set);
}

int hash_set_contains(hash_set_t hash_set, void *key, int hash(void *key,
		void *context), void *hash_context, int compare(void *x, void *y,
		void *context), void *compare_context)
{
	int index;
	linked_list_t key_list;

	_ASSERT(hash_set, ==, NULL, NULL_POINTER, -1);
	_ASSERT(hash, ==, NULL, NULL_POINTER, -1);

	index = hash(key, hash_context);
	key_list = vector_get_key_at(hash_set->back_bone, index);
	_ASSERT(key_list, ==, NULL, ELEMENT_NOT_FOUND, 0);

	return linked_list_search_key(key_list, key, compare, compare_context)
			== NULL;
}

void *hash_set_get_backbone(hash_set_t hash_set)
{
	_ASSERT(hash_set, ==, NULL, NULL_POINTER, NULL);

	return hash_set->back_bone;
}

void *hash_set_get_collision_list(hash_set_t hash_set, int hash_value)
{
	_ASSERT(hash_set, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(hash_value, <, 0, INVALID_INPUT, NULL);
	_ASSERT(hash_value, >=, vector_get_capacity(hash_set->back_bone), INVALID_INPUT, NULL);

	return vector_get_key_at(hash_set->back_bone, hash_value);
}

int hash_set_is_empty(hash_set_t hash_set)
{
	_ASSERT(hash_set, ==, NULL, NULL_POINTER, -1);

	return vector_get_capacity(hash_set->back_bone) == 0;
}

int hash_set_get_size(hash_set_t hash_set)
{
	long int size, sum, i;
	_ASSERT(hash_set, ==, NULL, NULL_POINTER, -1);

	size = vector_get_capacity(hash_set->back_bone);
	for (i = 0, sum = 0; i < size; i++)
		sum += linked_list_get_size(vector_get_key_at(hash_set->back_bone, i));

	return sum;
}

int hash_set_put(hash_set_t hash_set, void *key, int hash(void *key,
		void *context), void *hash_context, int compare(void *x, void *y,
		void *context), void *compare_context)
{
	int index;
	linked_list_t collided_keys;

	_ASSERT(hash_set, ==, NULL, NULL_POINTER, -1);
	_ASSERT(hash, ==, NULL, NULL_POINTER, -1);
	_ASSERT(compare, ==, NULL, NULL_POINTER, -1);

	index = hash(key, hash_context);
	collided_keys = vector_get_key_at(hash_set->back_bone, index);

	if (linked_list_search_key(collided_keys, key, compare, compare_context)
			== NULL)
	{
		linked_list_push_back(collided_keys, key);
		return 1;
	}
	return 0;
}

int hash_set_remove(hash_set_t hash_set, void *key, int hash(void *key,
		void *context), void *hash_context, int compare(void *x, void *y,
		void *context), void *compare_context)
{
	int index;
	linked_list_t collided_keys;
	linked_list_iterator_t it;

	_ASSERT(hash_set, ==, NULL, NULL_POINTER, -1);
	_ASSERT(hash, ==, NULL, NULL_POINTER, -1);
	_ASSERT(compare, ==, NULL, NULL_POINTER, -1);

	index = hash(key, hash_context);
	collided_keys = vector_get_key_at(hash_set->back_bone, index);

	it = linked_list_search_key(collided_keys, key, compare, compare_context);

	if (it != NULL)
	{
		linked_list_remove_iterator(collided_keys, it, 1);
		return 1;
	}
	return 0;
}

void hash_set_iterate(hash_set_t hash_set, void key_handler(void *key,
		void *context), void *context)
{
	int size, i;

	_ASSERT(hash_set, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	size = vector_get_size(hash_set->back_bone);

	for (i = 0; i < size; i++)
	{
		linked_list_iterate(vector_get_key_at(hash_set->back_bone, i),
				key_handler, context, 1);
		key_handler(NULL, context);
	}
}
